package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

/**
 * 用 Morris 遍历
 *
 * @author qidi
 * @date 2022-01-07 09:31:31
 */
class Q0114_FlattenBinaryTreeToLinkedList {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void flatten(TreeNode root) {
            if (root == null) return;

            TreeNode cur = root;

            while (cur != null) {
                if (cur.left != null) {
                    TreeNode subLeftRight = cur.left;
                    while (subLeftRight.right != null && subLeftRight.right != cur) {
                        subLeftRight = subLeftRight.right;
                    }
                    if (subLeftRight.right == null) {
                        subLeftRight.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
                        // 这里修改 morris 遍历
                        subLeftRight.right = cur.right;
                        cur.right = cur.left;
                        cur.left = null;
                        cur = subLeftRight;
                    }
                }
                cur = cur.right;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0114_FlattenBinaryTreeToLinkedList().new Solution();
        solution.flatten(BTreeUtil.getInstance().generateFromArray(1));
        solution.flatten(BTreeUtil.getInstance().generateFromArray(1, 2, 5, 3, 4, null, 6));
    }
}